package array;

import java.util.ArrayList;
import java.util.List;

public class leetCode79_exist {
    private boolean[][] visit;
    private int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}};
    int n = 0;
    int m = 0;
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0) return false;
        n = board.length;
        m = board[0].length;
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = true;
                if(build(board,0,i,j,word)){
                    return true;
                }
                visit[i][j] = false;
            }
        }

        return false;
    }

    public boolean build(char[][] board,int index,int x,int y,String word){
        if(index == word.length() - 1 && board[x][y] == word.charAt(index)){
            return true;
        }
        if(word.charAt(index) != board[x][y]){
            return false;
        }
        for (int k = 0; k < 4; k++) {
            int dI = direct[k][0] + x;
            int dJ = direct[k][1] + y;
            if(dI >= 0 && dI < n && dJ >= 0 && dJ < m && !visit[dI][dJ]){
                visit[dI][dJ] = true;
                if(build(board,index + 1,dI,dJ,word)){
                    return true;
                }
                visit[dI][dJ] = false;
            }
        }
        return false;
    }



}
